﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0068_NumSubarrayProductLessThanK : IAlgorithm
    {
        // 713. 乘积小于K的子数组

        // 给定一个正整数数组 nums和整数 k 。
        // 请找出该数组内乘积小于 k 的连续的子数组的个数。

        // 提示: 
        //  1 <= nums.length <= 3 * 10^4
        //  1 <= nums[i] <= 1000
        //  0 <= k <= 10^6

        public void Test()
        {
            // 算法参数定义
            int[] nums = new int[] { 10, 5, 2, 6 };
            int k = 100;
            // 算法执行与打印
            Console.WriteLine(NumSubarrayProductLessThanK(nums, k));
        }

        // 算法
        public int NumSubarrayProductLessThanK(int[] nums, int k)
        {
            if (nums == null || k == 0 || k == 1) 
                return 0;
            int left = 0, right = 0, prod = 1, res = 0;
            while (right < nums.Length)
            {
                prod *= nums[right];
                while (prod >= k)
                    prod /= nums[left++];
                res += right - left + 1;
                right++;
            }
            return res;
        }
    }
}
